# -*- coding: utf-8 -*-            
# @Time : 2023/2/22 23:12
# @Author  : lining
# @FileName: 二叉搜索树.py
"""
https://leetcode.cn/problems/validate-binary-search-tree/
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
所有左子树和右子树自身必须也是二叉搜索树。
      8
  4       10
3   6   9    11
思路：传入当前节点的值
（1）如果是左子树的左子树，就要比这个值小
（2）如果是左子树的右子树，就要比这个值大，并且小于这个值的父节点的值
（3）如果是右子树的左子树，就要比这个值小，并且大于这个值的父节点的值
（4）如果是右子树的右子树，就要比这个值大
大于最大值，小于最小值，不是二叉树
"""
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def isValidBst(node, left, right):
    if node is None:
        return True
    if node.val > left or node.val < right:
        return False
    left_result = isValidBst(node.left, node.val, right)
    if left_result is False:
        print(f'{node.val}左子树不是二叉搜索树')
        return False
    right_result = isValidBst(node.right, left, node.val)
    if right_result is False:
        print(f'{node.val}右子树不是二叉搜索树')
        return False
    return True


node5 = TreeNode(7)
node6 = TreeNode(9)
node2 = TreeNode(8, node5, node6)
node7 = TreeNode(11)
node8 = TreeNode(13)
node3 = TreeNode(12, node7, node8)
node4 = TreeNode(10, node2, node3)
node9 = TreeNode(0)

if isValidBst(node4, 999, -999):
    print('是二叉树')

